package com.situ.mall;

import org.junit.jupiter.api.Test;

public class Search {
    public static void main(String[] args) {
        int[] array = new int[] { 8, 17, 19, 37, 40, 73, 79, 82, 87, 95, 97, 98 };
        int target = 95;
        // 找到了返回索引位置，找不到返回-1
        int index = binarySearch(array, target);
        System.out.println(index);
    }

    private static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;
        int mid = (low + high) / 2;
        while (low <= high) {
            // 如果要查找的这个值在array里面有的话，那么一定会执行这个，
            // 最极端的情况就是low==high相等
            if (target == array[mid]) {
                return mid;
            }
            //没有找到，继续找
            if (target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                high = mid - 1;
            }

            mid = (low + high) / 2;
        }

        // 执行到这里代表在array里面没有找到元素
        return -1;
    }
}
